#include <stdio.h>
#include <stdlib.h>
#define LEN(x) sizeof(x) / sizeof(x[0])

//全局变量用来统计查找次数
int iCount = 0;

void popSort(int arr[], int len)
{

    for (int i = 0; i < len - 1; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int temp;
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int binarySearch(int arr[], int low, int high, int dest)
{
    if (low >= high)
    {
        return 0; //表示未找到该元素；
    }
    iCount++;
    int mid = (high + low) / 2;
    if (dest == arr[mid])
    {
        return 1;
    }
    if (dest < arr[mid])
    {
        return binarySearch(arr, low, mid - 1, dest);
    }
    if (dest > arr[mid])
    {
        return binarySearch(arr, mid + 1, high, dest);
    }
}

int search(int arr[], int len, int dest)
{
    popSort(arr, len); //首先对数组进行排序。

    return binarySearch(arr, 0, len, dest);
}

int main(int argc, char const *argv[])
{
    int arr[] = {23, 14, 8, 10, 18, 9, 33, 21, 17, 19, 4, 32};
    int dest = 4;
    int pos = search(arr, LEN(arr), dest);

    if (pos)
    {
        printf("找到元素：%d\n", dest);
    }
    else
    {
        printf("未找到元素：%d\n", dest);
    }
    printf("查找次数：%d", iCount);
    return 0;
}
